package 数据结构.LinkList.study;

// 定义单向链表
//我们并不需要将数据都知道，只要知道next是什么即可【所以最开始必须知道head节点】
//链表类：方便去管理链表【其实就是存head和size】
//mind：1.多设置暂时节点【十分的方便】
//      2.快慢指针
public class SingleLinkedList {
    // 头结点 :value next
    private Node head;
    // 链表的大小
    private int size;

    // 构造方法
    public SingleLinkedList() {
        this.head = null;
        this.size = 0;
    }

    // 节点类 (内部类)：有节点所要有的信息
    public class Node {
        // 值
        public int value;
        // 下一个节点的引用
        public Node next;

        // 构造方法初始化
        public Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // 头插法
    public void addFirst(int value) {
        // 创建新节点
        Node node = new Node(value);
        // 如果链表为空
        if (size == 0) {
            // 将新节点设为头节点
            this.head = node;
        } else {
            // 链表不为空，将新节点插入到头部
            //将当前node的下一指针位置设置为之前的head指针【这样就形成了 node -->head】
            //                                          在遍历的时候也是这样的
            node.next = head;
            //更新head指针 变为 head -->node1
            head = node;
        }
        // 增加链表长度
        this.size++;
    }
    //尾插法
    public void addLast(int value){
        Node node=new Node(value);
        if(size==0){
            this.head=node;
        }else {
            //因为我们只知道链表的头节点，所以每次都是拿头节点开刀
            //只有利用了头节点 和next才能知道下一个节点的信息
            Node temHead=this.head;//作用：避免弄完之后找不到head节点，所以暂时赋值
                                    //浅复制：即赋值后temHead和head将指向同一个空间
            //得到下一个节点
            Node current=temHead.next;
            //如果该节点不为null，则代表不是最后一个节点
            while (current!=null){
                //比如链表  2--> 1--> 3
                //这次的current为3，那么下一个current为null
                //所以要记录这个3的位置
                temHead=current;//这里将temHead和此时链表的尾节点指向同一个空间
                current=current.next;
            }
            //并将3的下一个节点的信息设为node，这样子就代表尾插了
            temHead.next=node;//然后这里将temHead的next指针指向node，
                                //那么上面链表的尾节点current的next也会指向node
        }
        this.size++;
    }

    //任意位置插入,注意：下标从0开始
    public boolean addIndex(int index,int value){
        //index为想要插入的位置 2--1-->3-->4;
        //                  如果index为2 value为5
        //                  则是想要将5节点插入到2位置
        //                  2--1-->5-->3-->4;
    //判断index是否合理【不能<0 / >链表的长度】
        if(index<0||index>this.size){
        System.out.println("不合理");
        return false;
    }
        //将value封装为节点
    Node node=new Node(value);
        //如果index为0，表示头插法
    if(index==0){
        node.next=this.head;
        head=node;
        this.size++;
        return true;
    }
    //2--1-->3-->4;
        //创建临时变量记录头结点,防止遍历后找不到头结点
        Node temHead=this.head;
    //这样子之后：得到的temHead将是想要插入的位置的前一个！！！
        //即temHead此时为1节点
        while (index>1){
            //将index去减，这样子方便得到要插入的位置
            index--;
            //将temHead的位置向前推
            temHead=temHead.next;
        }
        //将node的下一节点设为此时temHead的下一节点的节点：3
                //          node-->3-->4
        node.next=temHead.next;
        //将temHead的下一节点设为node
        //1-->node
        temHead.next=node;
        this.size++;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        //记录头节点
        Node tem=this.head;
        for (int i = 0; i < this.size; i++) {
            //判断是否相同，如果相同则返回true
            if(tem.value==key){
                return true;
            }
            tem=tem.next;
        }
        return false;
/*  如果不知道链表的长度
    遍历每一个结点
            利用!=null来判断是否到达了链表的结尾
        while (tem != null) {
            //如果找到,返回true
            if (tem.value == key) {
                return true;
            }
            tem = tem.next;
        }
        //未找到,返回 false
        return false;*/
    }
    //删除第一次出现关键字为key的节点【删除的概念：其实就是 2-->1-->3将2节点是下一节点指向3即可
    public void remove(int key){
        if(!contains(key)){
            System.out.println("不包含该元素");
        }
        //临时设置头节点
        Node tem=this.head;
        //如果要删除的是头节点 则重新定义头节点
        if(tem.value==key){
            head=tem.next;
            this.size--;
            return;
        }
        //定义前一个节点【方便去指向】
        Node temFront=tem;
        //当前节点
        tem=tem.next;
        for (int i = 1; i < this.size; i++) {
            //如果当前节点的值等于key
            if(tem.value==key){
                //则将前一个节点的指向给到当前节点的下一个节点【通过当前节点】
            temFront.next=tem.next;
            //todo：改变链表后记得将长度进行改变
            this.size--;
            return;
            }
            //如果不相等，则将节点往后移动
            temFront=tem;
            tem=tem.next;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(!contains(key)){
            System.out.println("不包含该元素");
        }
        //临时设置头节点
        Node tem=this.head;
        //如果要删除的是头节点 则重新定义头节点
        if(tem.value==key){
            head=tem.next;
            this.size--;
        }
        //定义前一个节点【方便去指向】
        Node temFront=tem;
        //当前节点
        tem=tem.next;
        while (tem!=null){
            //如果当前节点的值等于key
            if(tem.value==key){
                //则将前一个节点的指向给到当前节点的下一个节点【通过当前节点】
                temFront.next=tem.next;
                //todo：改变链表后记得将长度进行改变
                this.size--;
            }
            //如果不相等，则将节点往后移动
            //todo:注意：
            //这里不能是tem=tem.next;
            //         temFront=temFront.next;
            //如果是这样子的话2-->1-->3-->4
            //当前tem是1的话  那么temFront是2
            //然后temFront的下一个是1.tem的下一个是3【这个是之前没有被移除的情况下
            //如果之前有移除：temFront.next=tem.next;
            //那么现在temFront的下一个就是tem.next的下一个：3了
            //所以现在tem和temFront都指向了3，相同了
            //tem=tem.next;
            //    temFront=temFront.next;不行


            //如果是：下面这个则可以【先让tem赋值给当前的temFront
            //然后将tem=tem.next[避免了相同的情况，不用鼓励之前temFront.next是否被赋值了
            //                      这里直接将temFront重新赋值
            temFront=tem;
            tem=tem.next;
//            temFront=temFront.next;
        }
    }
    public void removeAllKey2(int key) {
        //多多利用设置节点，因为这里需要用到前一个和后一个，所以这里设置两个！
        Node now=this.head.next;
        Node per=this.head;
        while (now!=null){
            if(now.value==key){
                per.next=now.next;
                this.size--;
            }else {
                per=now;
            }
            now=now.next;
        }
        if(head.value==key){
            this.head=this.head.next;
        }
    }
        //清空链表
    public void clear(){
        //这里可以直接对头节点置空，相对于链表置空
 /*       this.head=null;
        this.size=0;*/
        //也可以对所有的节点进行置空
        this.size = 0;
        Node tmp;
        while (head.next != null) {
            tmp = this.head.next;
            //置空
            head.next = null;
            head = tmp;
        }
        this.head = null;
    }
    //反转链表:关键：将head.next设置为null【避免循环】
    public Node reverse(){
        if(this.size==0){
            System.out.println("链表为空");
            return null;
        }
        Node now=head.next;
        //这里将head.next设置为null，不然会在第一次的时候造成循环
        head.next=null;
        Node pre;
        while (now!=null){
            //如果没有将head.next设置为null
            //链表；2-->1-->3
            //第一次循环：2-->1
            //          2<--1，然后这里无限循环
            //pre的作用：暂时存储now.next的值
            pre=now.next;
            now.next=head;
            //这里的head=now后果：
            //head： value:1
            //           next:2【之前的head】
            //下一次循环：now：3
            //              next：1
            //                next:2
            //head： value：3
            //          next：1
            //              next:2
            head=now;
            now=pre;
        }
        return head;
    }
    //返回中间节点
    //利用快慢指针思想：一个走得快【一次走两步数】，一个走得慢【一次走一步】
    //这样子之后当fast指针为null时，slow就刚好到中间
    public Node middleNode(){
        Node fast=this.head;
        Node slow=this.head;
        //注意：这里fast.next也不能为null
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;

    }
    public void create(int []arr){
        if(arr.length == 0){
            return;
        }
        this.head= new Node(arr[0]);
        Node h=head;
        for (int i = 1; i < arr.length; i++) {
           Node tem = new Node(arr[i]);
            h.next=tem;
            h=tem;
        }
    }
    // 打印链表
    public void printList() {
        Node current = head; // 从头结点开始遍历
        System.out.println("head"+head);
        while (current != null) {
            System.out.print(current.value + " -> "); // 打印当前节点的值
            //根据指针的位置去进行遍历【因为上面在加的时候加了next的指向是哪个】
            current = current.next; // 移动到下一个节点
        }
        System.out.println("null"); // 打印链表尾部的 null
    }
    // 测试方法
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.addFirst(1);
        list.addFirst(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(4);
        list.addLast(4);
//        list.addIndex(2,5);
        System.out.println(list.contains(6));
        list.remove(1);
        list.removeAllKey2(4);
//        list.clear();
        //上面是将节点的next设置好
        //下面在遍历的时候，是根据node的next去遍历的【从head开始】
        list.printList(); // 打印链表
//        Node head = list.reverse();
        list.printList();
        System.out.println(list.middleNode().value);
        list.create(new int[]{2, 4, 6, 7});
        list.printList();
    }
}
